package com.krahets88.doublepointer;

import org.junit.jupiter.api.Test;

import java.util.List;

class ListNode {
    /**
     * 链表的定义
     */
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class Question160 {
    @Test
    public void test1() {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        System.out.println(access(node1, 0).val);
        System.out.println(access(reverseList(node1), 0).val);
    }
    @Test
    public void test2(){
        ListNode node1 = new ListNode(4);
        ListNode node2 = new ListNode(1);
        ListNode node3 = new ListNode(8);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        ListNode node7 = new ListNode(5);
        ListNode node8 = new ListNode(6);
        ListNode node9 = new ListNode(1);
        ListNode node10 = new ListNode(8);
        ListNode node11 = new ListNode(4);
        ListNode node12 = new ListNode(5);
        node7.next = node8;
        node8.next = node9;
        node9.next = node10;
        node10.next = node11;
        node11.next = node12;
        SolutionOne one = new SolutionOne();
        one.getIntersectionNode(node1,node7);
    }

    public ListNode access(ListNode head, int index) {
        /**
         * 访问链表的指定位置元素
         */
        for (int i = 0; i < index; i++) {
            if (head == null) {
                return null;
            }
            head = head.next;
        }
        return head;
    }

    public ListNode reverseList(ListNode head) {
        /**
         * 使用头插法源地逆序链表，首先要有头节点！
         */
        ListNode newHead = new ListNode(0);
        newHead.next = null;
        while (head != null) {
            ListNode nextNode = head.next;  // 保存下一个节点
            head.next = newHead.next; // 将当前节点插入到新链表的头部，当前节点指向新链表的下个位置
            newHead.next = head;  // 更新新链表的头部
            head = nextNode;    // 结束后，移动到下一个节点
        }
        return newHead.next;
    }

    class SolutionOne {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            if (headA == null || headB == null) {
                return null;
            }
            //获取一下两个链表的长度
            int alength = getListLength(headA);
            int blength = getListLength(headB);
            // 对齐两个指针
            if (alength - blength > 0) {
                for (int i = 0; i < (alength - blength); i++) {
                    headA = headA.next;
                }
            } else {
                for (int i = 0; i < (blength - alength); i++) {
                    headB = headB.next;
                }
            }
            ListNode start = null;
            while (true) {
                if (headA == null || headB == null) {
                    return start;
                }
                if (headA == headB && start == null) {
                    start = headA;
                }
                if (headA != headB) {
                    start = null;
                }
                headA = headA.next;
                headB = headB.next;
            }
        }

        public int getListLength(ListNode head) {
            int count = 0;
            while (head != null) {
                count++;
                head = head.next;
            }
            return count;
        }
    }

}
